package com.wuxuan.algorithm_homework.stackAndQueue;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 优先级括号匹配
 *
 * 给定一个只包括'('，')'，'[',  ']'，'{'，'}'的字符串s，括号的优先级排序由高到低依次为()，[]，{}，判断字符串是否有效。
 * 有效字符串需满足:
 * 左括号必须用相同类型的右括号闭合
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * 内层括号的优先级不低于外层括号。
 */
public class Q4 {
    // : "([{",由高到低排列
    public boolean isValid(String s, String priorityOrder) {
        if (s.length() % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        Map<Character, Integer> priorityMap = new HashMap<>();
        for (int i = 0; i < priorityOrder.length(); i++) {
            priorityMap.put(priorityOrder.charAt(i), priorityOrder.length() - i);
        }

        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                if (!stack.isEmpty() && priorityMap.get(c) < priorityMap.get(stack.peekFirst())) {
                    return false;
                }
                stack.offerLast(c);
            } else if (!stack.isEmpty() && c == map.get(stack.peekLast())) {
                stack.pollLast();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
